public class BinarySearchTree {
    //定义搜索二叉树的静态节点类
    //每个节点都有一个数值域，和左右子树
    static class Node{
        public int val;
        public Node left;
        public Node right;

        public Node(int key){
            this.val=key;
        }
    }


    //定义二叉搜索树的根节点
    public Node root;


    //搜索二叉树的节点的插入
    public boolean insert(int key){
        //判断是否为首次节点插入(即root是否为null)
        if(root==null){
            Node node=new Node(key);
            root=node;
            return true;
        }
        //如果不是第一次节点插入，那就要将节点插入到合适的叶子节点上(这是搜索二叉树节点的插入特点)
        Node parent=null;//用于当cur==null时，找到其父节点
        Node cur=root;
        while(cur!=null){
            //如果插入的元素大于当前cur节点，则cur节点向右树移动(反之向左移动)
            if(key>cur.val){
                parent=cur;
                cur=cur.right;
            }else if(key<cur.val){
                parent=cur;
                cur=cur.left;
            }else{
                System.out.println("插入失败(插入数据重复)");
                return false;
            }
        }

        //到这一步我们cur==null,此时我们就要考虑将该节点
        //加载到其parent节点的左树叶子节点还是右树叶子节点
        Node node=new Node(key);

        if(key> parent.val){
            parent.right=node;
            return true;
        }else{
            parent.left=node;
            return true;
        }
    }


    //查找搜索二叉树中的节点
    public Node search(int key){
        if(root==null)return null;
        Node cur=root;
        while(cur!=null){
            if(key>cur.val){
                cur=cur.right;
            }else if(key<cur.val){
                cur=cur.left;
            }else{
                return cur;
            }
        }
        return null;
    }

    //删除搜索二叉树中key值节点
    public void remove(int key){
        if(root==null)return;
        Node parent=null;
        Node cur=root;
        while(cur!=null){
            if(key>cur.val){
                parent=cur;
                cur=cur.right;
            }else if(key<cur.val){
                parent=cur;
                cur=cur.left;
            }else{
                //找到并删除节点
                removeNode(parent,cur);
            }
        }
    }

    //删除指定节点
    //重点思路是将情况分为3种情况(1:删除节点左树为null,右树不为null，2:删除节点右数为null,左树不为null,3:左右节点都不为空)
    public void removeNode(Node parent,Node cur){
        if(cur.left==null){
            //判断该节点是否为根节点
            if(cur==root){
                root=root.right;
            }else if(cur==parent.left){
                parent.left=cur.right;
            }else if(cur==parent.right){
                parent.right=cur.right;
            }
        }else if(cur.right==null){
            //判断是否为根节点
            if(cur==root){
                root.left=cur.left;
            }else if(cur==parent.left){
                parent.left=cur.left;
            }else if(cur==parent.right){
                parent.right=cur.left;
            }
        }else {
            Node target=cur.right;
            Node targetParent=cur;
            //找到cur节点右树的最小节点，存放在taarget变量中
            while(target.left!=null){
                targetParent=target;
                target=target.left;
            }
            //此处已经找到了cur节点右树的最小节点
            cur.val=target.val;
            //
            if(target==targetParent.left){
                targetParent.left=target.right;

            }else if(target==targetParent.right){
                targetParent.right=target.right;

            }
        }
    }

    //中序遍历搜索二叉树(从小到大)
    public void inOrder(Node root){
        if(root==null)return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
}
